package com.leecode.xiehf.page_01;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * <p>
 * 进阶：你能尝试使用一趟扫描实现吗？
 */
public class Solution_0019 {

    public static void main(String[] args) {
        Solution_0019 solution_0019 = new Solution_0019();
        ListNode result = solution_0019.removeNthFromEnd(
                new ListNode(1,
                        new ListNode(2,
                                new ListNode(3,
                                        new ListNode(4,
                                                new ListNode(5,
                                                        new ListNode(6,
                                                                new ListNode(7, null)
                                                        )
                                                )
                                        )
                                )
                        )
                ),
                7);
        System.out.println(result);
    }

    // 快慢指针
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        if (head == null || n == 0) {
            return head;
        }
        ListNode listNode = new ListNode(-1, head);
        ListNode fast = listNode;
        ListNode slow = listNode;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        if (fast == null) {
            return head;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return listNode.next;
    }

    // 倒数 那只能用递归了
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        n = next(head, n - 1);
        if (n == 0) {
            return head.next;
        }
        return head;
    }

    public int next(ListNode node, int n) {
        if (node.next == null) {
            return n;
        }
        n = next(node.next, n);
        if (n == 0) {
            node.next = node.next.next;
        }
        return n - 1;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

